package com.algorithm;

import java.util.Arrays;

/**
 * 选择排序-循环选出最小(大)，依次交换排
 * 从无序的数组中挑出最大（小）的排在最前面，之后剩下的依此规则再进行排序。
 * 注意:交换的是数组下标
 * @author Administrator
 *
 */
public class SelectionSort {

    public static int[] sort(int[] arrSource){
        int[] arr = Arrays.copyOf(arrSource,arrSource.length);
        for(int i=0;i<arr.length-1;i++){
            int min = i;//记录最小数的位置，默认为0
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min !=i){//说明有最小的值，位置在min，交换i,min
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
            System.out.println("排序中:"+Arrays.toString(arr));
        }
        return arr;
    }

    public static int[] sort2(int[] arrSource){
        int[] arr = Arrays.copyOf(arrSource,arrSource.length);
        for(int i=0;i<arr.length-1;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min!=i){
                int temp = arr[i];
                arr[i]=arr[min];
                arr[min] = temp;
            }
            System.out.println("排序中:"+Arrays.toString(arr));
        }
        return arr;

    }

    public static int[] sort3(int[] arraySource){
        int[] arr = Arrays.copyOf(arraySource,arraySource.length);
        for(int i=1;i<arr.length;i++){
            int min = i-1;
            for(int j=i;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min!=i-1){
                int temp = arr[min];
                arr[min] = arr[i-1];
                arr[i-1] = temp;
            }
            System.out.println("排序中sort3:"+Arrays.toString(arr));
        }
        return arr;
    }

    public static int[] sort4(int[] arrSource){
        int[] arr = Arrays.copyOf(arrSource,arrSource.length);
        for(int i=0;i<arr.length-1;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min!=i){
                int temp = arr[i];
                arr[i]= arr[min];
                arr[min] = temp;
            }
            System.out.println("排序中sort4:"+Arrays.toString(arr));
        }
        return arr;
    }

    public static void main(String[] args){

        int[] sort = new int[]{8,9,10,3,2,4,5,6,7,1};
        System.out.println("排序前:"+Arrays.toString(sort));
        System.out.println("排序后:"+Arrays.toString(sort4(sort)));

    }
}
